# coding:utf-8
# 题目：l=[1,2,3,4,5,6,7,8] 数据不重复，target=6，快速找出数组中两个元素之和等于target 的数组下标。

list1 = [1, 2, 3, 4, 5, 6, 7, 8]
set1 = set(list1)   # 使用集合已方便查找
target = 6

result = []
for a in list1:
    b = target - a
    if a < b < target and b in set1:   # 在集合中查找, 为避免重复，判断a为较小的那个值
        result.append((list1.index(a),  list1.index(b)))   # 列表index取下标的操作为O(1) 
print(result)

# 此题用两重for循环是最容易想到的，但是时间复杂度为 O(n^2)
# 最优解法是：利用字典或set的O(1)复杂度的特性，把时间复杂度降低，开辟一个set, 从set查找target与当前值的差，这个操作时间复杂度为O（1）
# 总的时间复杂度为O(n)